- Title
- On the period and tail of sequences of iterated eccentric digraphs
- Creator
- Gimbert, Joan; López, Nacho; Miller, Mirka; Ryan, Joseph
- Relation
- Bulletin of the Institute of Combinatorics and its Applications Vol. 56, p. 19-32
- Relation
- http://www.theica.org
- Publisher
- Institute of Combinatorics and its Applications
- Resource Type
- journal article
- Date
- 2009
- Description
- The eccentricity e(u) of a vertex u in a digraph G is the maximum distance from u to any other vertex in G. A vertex v is an eccentric vertex of u if the distance from u to v is equal to e(u). The eccentric digraph ED(G) of a digraph G has the same vertex set as G, but with an arc from u to v in ED(G) if and only if v is an eccentric vertex of u in G. Given a positive integer k, the kth iterated eccentric digraph of G is defined as EDk(G) = ED(EDk-1(G)), where ED0(G) = G. In this paper we study the behaviour of the sequence {EDk(G)}k when G is a labelled [unlabelled] digraph. More precisely, we investigate the [iso-]period and tail of G defined as the smallest integer numbers p > 0 and t ≥ 0 such that EDp+t(G) = EDt(G) [EDp+t(G) ≅ EDt(G)]. We derive that almost all digraphs have period two and tail zero. On the other hand, we show that there exist digraphs with arbitrarily large iso-period. We construct them using the generalized lexicographic product, taking as a basis an odd cycle graph. Additionally, we determine the period and tail of any tree, as well as other classes of graphs, by considering the connectivity of a certain subdigraph of ED(G) that 'concentrates' the eccentricities of all vertices of G.
- Subject
- eccentricity; eccentric vertex; eccentric digraph
- Identifier
- http://hdl.handle.net/1959.13/808904
- Identifier
- uon:7781
- Identifier
- ISSN:1183-1278
- Language
- eng
- Reviewed
- Hits: 4836
- Visitors: 5047
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|